1. Field of the Invention
The present invention generally relates to cache operations within computer systems, and more particularly to a cache replacement technique with adaptive skipping.
2. Description of the Related Art
Caching is a fundamental problem in computer science. Modern computational infrastructure designs are rich in examples of memory hierarchies where a fast, but expensive main (“cache”) memory is placed in front of an inexpensive, but slow auxiliary memory. Caching algorithms manage the contents of the cache so as to improve the overall performance. In particular, cache algorithms are of tremendous interest in databases, virtual memory management, and storage systems, etc., where the cache is RAM and the auxiliary memory is a disk subsystem.
For simplicity, it is assumed that both the cache and the auxiliary memory are managed in discrete, uniformly-sized units called “pages”. If a requested page is present in the cache, then it can be served quickly resulting in a “cache hit”. On the other hand, if a requested page is not present in the cache, then is must be retrieved from the auxiliary memory resulting in a “cache miss”. Usually, latency on a cache miss is significantly higher than that on a cache hit. Hence, caching algorithms focus on improving the hit ratio. Historically, the assumption of “demand paging” has been used to study cache algorithms. Under demand paging, a page is retrieved from the auxiliary memory to the cache only on a cache miss. In other words, demand paging precludes speculatively pre-fetching pages. Under demand paging, the only question of interest is: When the cache is full, and a new page must be inserted in the cache, which page should be replaced?
Digital microprocessors use cache memory to hold data likely to be needed in the near future. Cache memory is comparatively fast and is a local memory. Caching usually occurs when data or other instructions are retrieved from the main memory to be used by the microprocessor, they are also stored in the cache. Typically, the cache is constructed from a random access, read/write memory block (RAM), which can access a single stored object, referred to a line, in a single processor cycle. Preferably, the cache size matches the processor cycle time and is read or written during a given cycle. A server can be configured to receive a stream of requests from clients in a network system to read from or write to a disk drive in the server. These requests form the “workload” for the server.
Each line in the cache memory contains the data being saved and the address of the data in the main memory (the tag). An example of a simple cache 210 is illustrated in the block diagram of FIG. 1. When the microprocessor makes a reference to the main memory, a part of the reference address, referred to as the index, accesses a single line stored in the cache RAM 212. A “hit” occurs if the tag of the accessed line in the cache 210 matches the reference address of the referenced data. When this happens the cache RAM 212 immediately supplies the line to the microprocessor. However, a “miss” occurs if the tag of the accessed line in the cache 210 does not match the reference address of the referenced data. When this happens the address is sent to the main memory to retrieve the requested line. When the main memory sends the line to the microprocessor, it is written into the cache RAM 212 using the same index as the original look-up, along with its tag. However, because the main memory is much slower than the microprocessor, a delay occurs during this retrieval process.
Additionally, cache memory is used when data is written from a host computer to a long-term data storage device such as a disk drive. Here, data may be written to cache memory in which it is temporarily held with an indication that the data must be written to longer term data storage when the data storage system is able to perform this write operation. When cache memory is used to temporarily delay write pending data, memory storage locations are removed from the main memory locations generally available to the data storage system in which data may be held pending use by the host.
Traditionally, under the assumption of demand paging, a cache technique termed the least recently used (LRU) has been used. When the cache is full, and a page must be demoted to make for a new page, LRU removes the least recently used page from the cache. The LRU technique is simple to implement, has low space and time overhead, and it captures “clustered locality of reference” or “recency” property of workloads. However, LRU has two main disadvantages: (i) it does not capture pages with “high frequency” or “long-term-utility” and (ii) it is not resistant to scans which are a sequence of one-time-use-only read/write requests.
Recently, under the assumption of demand paging, a cache technique termed the Adaptive Replacement Cache (ARC) has been used (Nimrod Megiddo and D. S. Modha, ARC: A Self-tuning, Low Overhead Replacement Cache, Proc. 2nd USENIX Conference on File and Storage Technologies (FAST 03), San Francisco, Calif. 115-130, 2003), the complete disclosure of which is herein incorporated by reference. Comparatively, this caching technique has low computational overhead similar to LRU updating schemes, its space overhead over LRU is negligible, it outperforms LRU for a wide range of workloads and cache sizes, it is self-tuning in that for every workload it dynamically adapts between recency and frequency to increase the hit ratio, and it is scan-resistant, and, hence, avoids cache pollution due to sequential workloads.
The below-referenced U.S. Patents disclose embodiments that were satisfactory for the purpose for which they were intended. The disclosures of the below-referenced prior U.S. Patents, in their entireties, are hereby expressly incorporated by reference into the present invention for purposes including, but not limited to, indicating the background of the present invention and illustrating the state of the art.
U.S. Pat. No. 5,285,527 discloses a predictive cache that attempts to guess which instructions will be used by a processor. U.S. Pat. No. 5,043,870 deals with a stack cache inside a processor and provides solutions of how to allocate limited machine registers inside a processor. U.S. Pat. No. 5,584,009 provides a system and method of retiring stored data from a write buffer. CLOCK is a cache replacement technique that is widely used in databases and computer operating systems, see, for example, Andrew S. Tanenbaum and A. S. Woodhull Operating Systems: Design and Implementation, Prentice-Hall, 1997, the complete disclosure of which is herein incorporated by reference. Page replacement in cache occurs when there are no free frames available, and the operating system must replace (evict) a page (victim), removing it from memory to reside only on disk (back store). With regards to replacement techniques, the goal is for the replacement technique to choose the best victim, with the metric for the “best” reducing the fault rate. In a clock replacement technique, a circular queue is maintained with a pointer to the next candidate (clock hand). At fault time operations occur including scanning around the clock, looking for page with usage bit of zero (victim), and clearing usage bits as they are passed. Thus, it is known whether or not a page has been used since the last time the bits were cleared. However, CLOCK suffers from some limitations such as lack of resistance to scans, low performance, and disregard for frequency. Therefore, there is a need for a new cache replacement technique that dynamically tunes itself to adapt to an evolving workload, is scan-resistant, and out-performs CLOCK. Moreover, in the same way that ARC improved on LRU while using the same data structures that are used by LRU, there is a pressing need for a technique like ARC that improves upon CLOCK while using the same data structures that are used by CLOCK.